#include <malloc.h>
#include "stdio.h"

/**
 * 定义三元组（a,b,c）(a,b,c均为整数)的距离D=|a-b|+|b-c|+|c-a|。给定3个非空整数集合S1，S2，S3，按升序分别储存3个数组中。
 * 请设计一个尽可能高效的算法，计算并输出所有可能的三元组（a,b,c）（a∈S1，b∈S2，C∈S3）中的最小距离。
 * 列如S1={-1,0,9}，S2={-25，-10,10，11}，S3={2,9,17,30,41}则最小距离为2，相应的三元组为（9,10,9）
 * 要求：
 * （1）给出算法的基本设计思想。
 * （2）根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。
 * （3）说明你所设计算法的时间复杂度和空间复杂度。
 */

int abs(int a) {
    if (a < 0) {
        return -a;
    }
    return a;
}

int distance(int a, int b, int c) {
    return abs(a - b) + abs(b - c) + abs(c - a);
}

int minDistance(int *a, int *b, int *c,int lengtha,int lengthb,int lengthc) {
    // 定义三个指针
    int i = 0;
    int j = 0;
    int k = 0;
    int result = INT_MAX;
    while (i < lengtha && j < lengthb && k < lengthc) {
        int ai = a[i];
        int bi = b[j];
        int ci = c[k];
        printf("%d %d %d\n",ai,bi,ci);
        // 计算当前三元组的距离
        int now = distance(ai, bi, ci);
        // 更新最小距离
        if (now < result) {
            result = now;
        }
        // 移动指向最小值的指针
        if (ai <= bi && ai <= ci) {
            i++;
        } else if (bi <= ai && bi <= ci) {
            j++;
        } else {
            k++;
        }
    }
    return result;
}

int main() {
    int a[] = {1, 2, 6};
    int b[] = {4, 5, 6, 7};
    int c[] = {8, 9, 10, 30, 41};
//    int a[] = {-1, 0, 9};
//    int b[] = {-25, -10, 10, 11};
//    int c[] = {2, 9, 17, 30, 41};
    int result = minDistance(a, b, c,
                             sizeof(a) / sizeof(a[0]),
                             sizeof(b) / sizeof(b[0]),
                             sizeof(c) / sizeof(c[0])
                             );
    printf("%d",result);
    return 0;
}

